Word Ladder I II (LeetCode)

文章目录

1. 1. I
   1. 1.1. Question:Word Ladder I
   2. 1.2. SourceCode:
      1. 1.2.1. s1
      2. 1.2.2. s2
2. 2. II
   1. 2.1. Question:Word Ladder II
   2. 2.2. SourceCode:
      1. 2.2.1. s1
      2. 2.2.2. s2

I

Question:Word Ladder I

Given two words (beginWord and endWord), and a dictionary's word list, find the 

length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time;Each intermediate word must exist in the 

word list

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.    

SourceCode:

s1

//笔者提交版本；耗时：ms；
//BFS
//So we quickly realize that this is a search problem, and breath-first search guarantees the optimal //solution.
public class Solution {
    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
        return  solution(beginWord, endWord, wordList);
    }
    
    
    class wordNode{
		int numSteps;
		String word;
		public wordNode(int numSteps,String word){
			this.numSteps = numSteps;
			this.word = word;
		}
	}
	
	private int solution(String beginWord, String endWord, Set<String> wordList) {
		LinkedList<wordNode> queue = new LinkedList<>();
		queue.add(new wordNode(1, beginWord));
		wordList.add(endWord);
		
		while(!queue.isEmpty()){
			wordNode tmpWordNode = queue.remove();
			
			if(endWord.equals(tmpWordNode.word)){
				return tmpWordNode.numSteps;
			}
			
			char[] wordChars = tmpWordNode.word.toCharArray();
			for(int i = 0 ; i < wordChars.length;i++){
				char tmpChar = wordChars[i];
				for(char c = 'a';c <= 'z';c++){
					wordChars[i] = c;
					
					String comWord = new String(wordChars);
					if(wordList.contains(comWord)){
						queue.add(new wordNode(tmpWordNode.numSteps+1,comWord ));
						wordList.remove(comWord);
					}
				}
				
				wordChars[i] = tmpChar;
			}
		}
		
		
		return 0;
	}

    
    
}

s2

//该版本参考了Discuss,还没看Discuss；耗时：ms；
//待写

II

Question:Word Ladder II

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation 

sequence(s) from beginWord to endWord, such that:

Only one letter can be changed at a time
Each intermediate word must exist in the word list

For example,
Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Return
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]

Note:

All words have the same length.
All words contain only lowercase alphabetic characters.    

SourceCode:

s1

//笔者提交版本；耗时：；
//BFS
//The idea is the same. To track the actual ladder, we need to add a pointer that points to the previous node in the WordNode class.
//In addition, the used word can not directly removed from the dictionary. The used word is only removed when steps change.
public class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {
        return solution(beginWord,endWord,wordList);
    }
    

    class wordNode{
		int numSteps;
		String word;
		wordNode pre;
		public wordNode(String word,wordNode pre,int numSteps){
			this.numSteps = numSteps; //层次 root 为第 1 层
			this.word = word;
			this.pre = pre;
		}
	}
	
	private List<List<String>> solution(String beginWord, String endWord, Set<String> wordList){
		LinkedList<wordNode> queue = new LinkedList<>();
		queue.add(new wordNode(beginWord, null,1));
		wordList.add(endWord);
		List<List<String>> result = new LinkedList<>();
		int minStep = 0;//最小层数一定最先遍历到；因为是按层次遍历；
		int preNumsteps = 0; //定义每一次遍历的前一次遍历层次；
		
		Set<String> visited = new HashSet<>();
		Set<String> unVisited = new HashSet<>(wordList);
		
		while(!queue.isEmpty()){
			wordNode tmpWord = queue.remove();
			String word = tmpWord.word;
			if(word.equals(endWord)){
				
				if(minStep == 0){
					minStep = tmpWord.numSteps;
				}
					
				if(minStep == tmpWord.numSteps && minStep != 0){
					
					LinkedList<String> tmpResult = new LinkedList<>();
					wordNode tmpNode = tmpWord;
					while(null != tmpNode){
						tmpResult.addFirst(tmpNode.word);
						tmpNode = tmpNode.pre;
					}
					result.add(tmpResult);
				}
				
				continue;
			}
			
			//将当前层次（包括）之前的所用过的节点排除；
			if(preNumsteps < tmpWord.numSteps){
				unVisited.removeAll(visited);
			}
			preNumsteps = tmpWord.numSteps;
			
			
			char[] wordChars = tmpWord.word.toCharArray();
			for(int i = 0 ; i < wordChars.length;i++){
				char tmpChar = wordChars[i];
				for(char c = 'a';c <= 'z';c++){
					wordChars[i] = c;
					
					String comWord = new String(wordChars);
					
					if(unVisited.contains(comWord)){
						queue.add(new wordNode(comWord,tmpWord,tmpWord.numSteps+1));
						/*if(!endWord.equals(comWord)){
							wordList.remove(comWord);
						}*/
						visited.add(comWord);
					}
				}
				
				wordChars[i] = tmpChar;
			}
			
		}
		
		
		return result;
	}
    
    
}

s2

//该版本参考了Discuss,还没看Discuss；耗时：ms；
//待写